//https://leetcode.cn/problems/generate-parentheses/
//生成有效且不重复的括号对
//递归，回溯，
//想一个一个的子问题是想不出来的，把边界情况和非边界情况处理正确就能解决问题
class Solution {
public:
    vector<string> ret;
    void dfs(const string& res,int left,int right)
    {
        if(left<0||left>right)
        {
            return;
        }
        if(left==0&&right==0)
        {
            ret.push_back(res);
            return;
        }
        dfs(res+'(',left-1,right);
        dfs(res+')',left,right-1);
    }
    vector<string> generateParenthesis(int n) {
        dfs("",n,n);
        return ret;
    }
};
